<html>
<head><meta charset="utf-8"><title>Dev Guide + Dataflow + Convergence · t-compiler · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/index.html">t-compiler</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html">Dev Guide + Dataflow + Convergence</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="218092961"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218092961" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218092961">(Nov 27 2020 at 13:39)</a>:</h4>
<p>Pinging <span class="user-mention" data-user-id="307537">@Camelid</span>, since I think they were involved in this part of the Dev Guide.</p>



<a name="218093036"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218093036" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218093036">(Nov 27 2020 at 13:40)</a>:</h4>
<p>(deleted)</p>



<a name="218093481"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218093481" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218093481">(Nov 27 2020 at 13:44)</a>:</h4>
<p>So on <a href="https://rustc-dev-guide.rust-lang.org/mir/dataflow.html#convergence">this part of the dev guide</a> it is stated that:</p>
<blockquote>
<p>Having a top value ensures that your semilattice has a finite height, and the law state above ensures that once the dataflow state reaches top, it will no longer change (the fixpoint will be top).</p>
</blockquote>
<p>Which I'm not entirely sure is the case?</p>
<p>As I've understood it, there are lattices with both a top and bottom value which have infinite height (think of the natural numbers with the partial order of divisibility: a | b &lt;----&gt; "a divides b", which has top and bottom elements (bottom is 1, and top is 0) but is infinite in height). So, I think I'm missing a third restriction over the lattice, that forces its height to be finite... but it might be implicit in the document or it might be missing. I'm not sure which.</p>
<p>Sorry if what I'm asking is too obvious &gt;.&lt; but I want to know if we're on the same page, so that I can move forward with learning the dataflow tools :3</p>



<a name="218094386"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218094386" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218094386">(Nov 27 2020 at 13:53)</a>:</h4>
<p>The dataflow framework docs explain this in a different way: <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/trait.Analysis.html#convergence">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir/dataflow/trait.Analysis.html#convergence</a></p>



<a name="218094875"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218094875" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218094875">(Nov 27 2020 at 13:57)</a>:</h4>
<p>Note that convergence is a non-issue when writing only gen-kill analyses, which cover the majority of dataflow analyses you might want to do</p>



<a name="218099995"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218099995" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218099995">(Nov 27 2020 at 14:53)</a>:</h4>
<p>You mean monotonicity? <span class="user-mention" data-user-id="211727">@Jonas Schievink</span></p>



<a name="218100104"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100104" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100104">(Nov 27 2020 at 14:54)</a>:</h4>
<p>If I'm understanding it correctly, monotonicity would still require a finite domain</p>



<a name="218100157"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100157" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100157">(Nov 27 2020 at 14:54)</a>:</h4>
<p>hmm, the docs seem to imply convergence, but I'm not sure</p>



<a name="218100240"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100240" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100240">(Nov 27 2020 at 14:55)</a>:</h4>
<blockquote>
<p>when writing only gen-kill analyses, which cover the majority of dataflow analyses you might want to do</p>
</blockquote>
<p>I'm actually not sure if where I'm headed with the constprop augmentation, a gen-kill analysis is all that I'll need. Although that would be pretty nice :3</p>



<a name="218100336"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100336" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100336">(Nov 27 2020 at 14:56)</a>:</h4>
<p>oh, if you're adding range analysis then you need more</p>



<a name="218100391"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100391" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100391">(Nov 27 2020 at 14:57)</a>:</h4>
<p>Yeah, I was thinking the other day that this tool fits what I think value range analysis would need</p>



<a name="218100440"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100440" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100440">(Nov 27 2020 at 14:57)</a>:</h4>
<p>And thus I might be able to get away with both doing VRA and supporting a better constprop through the same analysis</p>



<a name="218100505"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100505" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100505">(Nov 27 2020 at 14:58)</a>:</h4>
<p>(VRA in this case would be almost a superset of constprop, right?)</p>



<a name="218100615"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218100615" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218100615">(Nov 27 2020 at 14:59)</a>:</h4>
<p>BTW I don't remember which module it was, but yesterday I was studying dataflow with this playlist (linked by the dataflow docs in the dev guide :3) <a href="https://www.youtube.com/watch?v=NVBQSR_HdL0&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=2">https://www.youtube.com/watch?v=NVBQSR_HdL0&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=2</a><br>
And there they mentioned the issue of needing a finite domain. I'm gonna dig up the exact slide, but there's where I learned about that</p>
<div class="youtube-video message_inline_image"><a data-id="NVBQSR_HdL0" href="https://www.youtube.com/watch?v=NVBQSR_HdL0&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=2"><img src="https://i.ytimg.com/vi/NVBQSR_HdL0/default.jpg"></a></div>



<a name="218101537"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218101537" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218101537">(Nov 27 2020 at 15:08)</a>:</h4>
<p>Alright, found it. Here are all the restrictions that they stated to ensure termination: <br>
<a href="https://www.youtube.com/watch?v=fWoc2bZZ59A&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=3&amp;t=9m34s">https://www.youtube.com/watch?v=fWoc2bZZ59A&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=3&amp;t=9m34s</a></p>
<div class="youtube-video message_inline_image"><a data-id="fWoc2bZZ59A" href="https://www.youtube.com/watch?v=fWoc2bZZ59A&amp;list=PL_sGR8T76Y58l3Gck3ZwIIHLWEmXrOLV_&amp;index=3&amp;t=9m34s"><img src="https://i.ytimg.com/vi/fWoc2bZZ59A/default.jpg"></a></div><ol>
<li>A complete lattice (so, a partial order, a Top element, a Bottom element, and join_b(x, y) is <code>x |_| y</code> for all b.</li>
<li>Trans_b is monotonic (so, if <code>x &lt;= y</code>, then <code>trans_b(x) &lt;= trans_b(y)</code>)</li>
<li>And the last one that seals the deal, <strong>finite lattice height</strong>. So not entirely a finite domain (you could have e.g. infinite width in some or all levels of the lattice, but the amount of steps that separate Bottom from Top is finite).</li>
</ol>



<a name="218118179"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218118179" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218118179">(Nov 27 2020 at 18:16)</a>:</h4>
<p>(<span class="user-mention" data-user-id="211727">@Jonas Schievink</span>)</p>



<a name="218118324"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218118324" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218118324">(Nov 27 2020 at 18:18)</a>:</h4>
<p>Sounds correct to me, but I'm not that well-versed in dataflow</p>



<a name="218120053"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218120053" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218120053">(Nov 27 2020 at 18:46)</a>:</h4>
<p><span class="user-mention" data-user-id="212698">@Félix Fischer</span> Please open a PR to the dev-guide with <code>r? @oli-obk</code> if that section is incorrect :)</p>



<a name="218123501"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218123501" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218123501">(Nov 27 2020 at 19:36)</a>:</h4>
<p>Ahhh, but <span class="user-mention" data-user-id="307537">@Camelid</span> I'm not entirely sure if it's incorrect, that's why I pinged you here, since you were the last editor of that section and I'd assumed that maybe you knew the answer :)</p>



<a name="218124249"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218124249" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218124249">(Nov 27 2020 at 19:46)</a>:</h4>
<p>I'm not sure either :)</p>
<p>I'm quite new to data-flow analysis (I learned from this videos that you referenced); I've been trying to understand it, but I think you know more than I.</p>



<a name="218124535"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218124535" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218124535">(Nov 27 2020 at 19:51)</a>:</h4>
<p>Oh noes, I'm also new to data-flow analysis (although the lattice topic is close to other discrete math things that I'm very familiar with, so maybe that's where I give the impression x3)</p>
<p>Tell you what. Shall I open a PR and then we ask others that are involved in that, for review?<br>
I should open one regardless, since I want to put a link to the Wikipedia article about semi-lattices (since they are mentioned but only the Lattice article is linked to) :)</p>



<a name="218127650"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/218127650" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Noah Lev <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#218127650">(Nov 27 2020 at 20:39)</a>:</h4>
<p>Sounds like a deal :)</p>



<a name="220149533"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/131828-t-compiler/topic/Dev%20Guide%20%2B%20Dataflow%20%2B%20Convergence/near/220149533" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Félix Fischer <a href="https://rust-lang.github.io/zulip_archive/stream/131828-t-compiler/topic/Dev.20Guide.20.2B.20Dataflow.20.2B.20Convergence.html#220149533">(Dec 16 2020 at 17:55)</a>:</h4>
<p>Well, I ended up opening an Issue describing all my nitpicks with that section. <span class="user-mention" data-user-id="307537">@Camelid</span> take a look <span aria-label="smile" class="emoji emoji-1f642" role="img" title="smile">:smile:</span>  <a href="https://github.com/rust-lang/rustc-dev-guide/issues/990">https://github.com/rust-lang/rustc-dev-guide/issues/990</a></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>